package DFS;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @Author: dust
 * @Date: 2019/11/24 17:02
 */
public class EulerLoop {

    private Graph G;

    public EulerLoop(Graph g) {
        G = g;
    }

    public boolean hasEulerLoop(){
        CC cc=new CC(G);
        if(cc.count()>1)
            return false;
        for(int v=0;v<G.V();v++){
            if(G.degree(v)%2==1){
                return false;
            }
        }
        return true;
    }

    public ArrayList<Integer> result(){
        ArrayList<Integer>res=new ArrayList<>();
        if(!hasEulerLoop())return res;
        Graph g=(Graph)G.clone();
        Stack<Integer>stack=new Stack<>();
        int curv=0;
        stack.push(curv);
        while (!stack.isEmpty()){
            if(g.degree(curv)!=0){
                stack.push(curv);
                int w=g.adj(curv).iterator().next();
                g.removeEdge(curv,w);
                curv=w;
            }else{
                res.add(curv);
                curv=stack.pop();
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Graph g=new Graph("g6.txt");
        EulerLoop eulerLoop=new EulerLoop(g);
        System.out.println(eulerLoop.result());

    }
}
